<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        let arr = [70,67,49,35,59,98,100,20];
        // 选择
        function selectSort(arr){
            for(let i = 0;i < arr.length;++i){
                let flag = true; // 是否已经有序的标记
                for(let j = i+1;j < arr.length;++j){
                    if(arr[i] < arr[j]){
                        swap(arr,i,j);
                        flag = false;
                    }  
                }
                if(flag) break;
            }
            document.write(arr);
        }

        // 插入
        function insertSort(arr){
            for(let i = 1;i < arr.length;++i){
                // 找到插入位置
                for(let j = i;j > 0;--j){
                    if(arr[j] > arr[j-1]){
                        swap(arr,j,j-1);
                    }
                }
            }
            document.write(arr);
        }
        // 快排
        function qsort(arr){
            qsortChild(arr,0,arr.length-1);
            document.write(arr);
        }
        function qsortChild(arr, l, r){
            if(l >= r) return;
            let left = l-1,right = r+1,i = l;
            let ran = Math.floor(Math.random()*(r-l+1));
            let k = arr[ran+l];
            // 数组分三块
            while(i < right){
                if(arr[i] > k) swap(arr,++left,i++);
                else if(arr[i] < k) swap(arr,--right,i);
                else ++i;
            }
            qsortChild(arr,l,left);
            qsortChild(arr,right,r);
        }

        // 归并
        function mergeSort(arr){

        }
        // 冒泡
        function bubbleSort(arr){
            // 轮数
            for(let i = 0;i < arr.length;++i){
                let flag = true; // 是否已经有序的标记
                // 每轮比较次数
                for(let j = arr.length - 1;j > i;--j){
                    if(arr[j] > arr[j-1]){
                        swap(arr,j,j-1);
                        flag = false;
                    }
                }
                if(flag) break;
            }
            document.write(arr);
        }
        function swap(arr,i,j){
            let t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
        // selectSort(arr);
        // bubbleSort(arr);
        // insertSort(arr);
        // document.write(arr);
        qsort(arr);
    
    </script>
</body>
</html>